package cn.jzq.sort;

import java.util.Arrays;

public class RecursionInsertionSort
{
    /**
     *
     * @param array  需要排序的数组
     * @param p 起始索引
     * @param q 结束索引
     */
    public static void recursionInsertionSort(int[] array, int p, int q)
    {
        if (p < q)
        {
            recursionInsertionSort(array, p, q - 1);
            insert(array, p, q - 1);
        }
    }

    /**
     *
     * @param p 开始索引
     * @param q 结束索引
     */
    public static void insert(int[] array, int p, int q)
    {
        int key = array[q]; // 需要排序的值
        int i = q - 1;
        while (i >=0 && array[i] > key)
        {
            array[i + 1] = array[i];
            i--;
        }
        array[i + 1] = key;
    }


    public static void main(String[] args)
    {
        int[] arr = new int[12];
        for (int i = 0; i < 12; i++)
        {
            arr[i] = (int) (Math.random() * 100) + 1;
        }
        long start = System.currentTimeMillis();
        recursionInsertionSort(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));
        long end = System.currentTimeMillis();

        System.out.println("用时 : " + (end - start) + " ms");
    }
} 
